/**
 * By replacing each of the letters in the word CARE with 1, 2, 9, and 6
 * respectively, we form a square number: 1296 = 36^2. What is remarkable 
 * is that, by using the same digital substitutions, the anagram, RACE, 
 * also forms a square number: 9216 = 96^2. We shall call CARE (and RACE) 
 * a square anagram word pair and specify further that leading zeroes are 
 * not permitted, neither may a different letter have the same digital 
 * value as another letter.
 *
 * Using words.txt, a 16K text file containing nearly two-thousand common 
 * English words, find all the square anagram word pairs (a palindromic 
 * word is NOT considered to be an anagram of itself).
 *
 * What is the largest square number formed by any member of such a pair?
 *
 * NOTE: All anagrams formed must be contained in the given text file.
 */

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include "euler/permutation.hpp"
#include "euler/digits.hpp"
#include "euler.h"

BEGIN_PROBLEM(98, solve_problem_98)
	PROBLEM_TITLE("Words and their anagrams that represents square numbers")
	PROBLEM_ANSWER("18769")
	PROBLEM_DIFFICULTY(2)
	PROBLEM_FUN_LEVEL(2)
	PROBLEM_TIME_COMPLEXITY("?")
	PROBLEM_SPACE_COMPLEXITY("?")
	PROBLEM_KEYWORDS("text processing")
END_PROBLEM()

static const char * Words[] = {
#include "../input/words.txt"
};

typedef euler::permutation<unsigned char> permutation_t;

// To find the complexity of the algorithm, 
// - Let L=14 be the length of the longest word, and
// - Let N=2000+ be the number of words.

// Represents the structure of a word.
// @timecomplexity  O(L*log(L))
// @spacecomplexity O(L).
class word_struct
{
	std::string _word;   // the word
	std::string _sorted; // sorted letters in the word
	permutation_t _perm; // permutation p such that p(word)=sorted.
	std::string _mask;   // letters replaced by digits starting from 1.

public:

	word_struct(const std::string &s) : _word(s), // _sorted(s),
		_perm(permutation_t::reorder(_word.begin(),_word.end()))
	{ 
		sort();
		build_mask();
	}

	// Sort the letters in the word.
	void sort()
	{
		//_perm = euler::sort_permutation<unsigned char>(_word.begin(), _word.end());
		auto x = _perm(_word.begin(), _word.end());
		_sorted.assign(x.begin(), x.end());
	}

	// Build the mask. For example, RECENT->123245
	void build_mask()
	{
		auto pinv = _perm.inverse();

		char id = '0';
		_mask.resize(_word.size());
		std::string sorted_mask(_mask);
		for (int i = 0; i < (int)_word.size(); i++)
		{
			size_t k = pinv[i];
			if (k > 0 && _sorted[k] == _sorted[k-1])
				_mask[i] = sorted_mask[k] = sorted_mask[k-1];
			else
				_mask[i] = sorted_mask[k] = ++id;
		}
	}

	size_t size() const { return _word.size(); }
	const std::string& word() const { return _word; }
	const std::string& sorted() const { 	return _sorted; 	}
	const permutation_t& perm() const { return _perm; }
	const std::string& mask() const { return _mask; }
};

#if 0
struct word_pair : public std::pair<word_struct,word_struct>
{
	// Permutation h such that word2 = h(word1).
	// Since we assume that sorted1 == sorted2, and
	// sorted1 = perm1(word1), sorted2 = perm2(word2),
	// we have word2 = perm2^{-1}(sorted2) = perm2^{-1}(perm1(word1)).
	permutation_t perm;

	word_pair(const word_struct &w1, const word_struct &w2)
		: std::pair<word_struct,word_struct>(w1, w2),
		perm(w1.perm(), w2.perm().inverse()) { }

	word_pair(const word_struct &w)
		: std::pair<word_struct,word_struct>(w, w), 
		perm(w.size()) { }
};
#else
// @spacecomplexity O(L)
// @timecomplexity  O(L)
struct word_pair
{
	// Permutation h such that word2 = h(word1).
	// Since we assume that sorted1 == sorted2, and
	// sorted1 = perm1(word1), sorted2 = perm2(word2),
	// we have word2 = perm2^{-1}(sorted2) = perm2^{-1}(perm1(word1)).
	std::string _word;
	std::string _mask;
	permutation_t _perm;

	word_pair(const word_struct &w1, const word_struct &w2)
		: _word(w1.word()), _mask(w1.mask()),
		_perm(w1.perm(), w2.perm().inverse()) { }

	word_pair(const word_struct &w)
		: _word(w.word()), _mask(w.mask()), _perm() { }

	const std::string& word() const { return _word; }
	const std::string& mask() const { return _mask; }
	const permutation_t& perm() const { return _perm; }
};
#endif

// Define an order for word pairs. 
// It is first sorted by the first word's mask.
// If the two masks are equal, it's sorted by the lexigraphical order of
// the permutation that maps word1 to word2.
// @timecomplexity O(L)
bool operator < (const word_pair &p1, const word_pair &p2)
{
	if (p1.mask() < p2.mask())
		return true;
	if (p2.mask() < p1.mask())
		return false;
	return p1.perm() < p2.perm();
}

// @timecomplexity O(L n^2 log mn) where n = end - begin, m = filter.size().
// @spacecomplexity O(L n^2)
static void find_anagram_pairs(
	std::vector<word_struct>::iterator begin,
	std::vector<word_struct>::iterator end,
	std::vector<word_pair> &word_pairs,
	const std::vector<word_pair> &filter)
{
	// Sort the words by the letters they contain.
	// @timecomplexity: O(L n log(n))
	// std::cout << "Sorting " << end - begin << " words." << std::endl;
	std::sort(begin, end, [](const word_struct &w1, const word_struct &w2) -> bool {
		return w1.sorted() < w2.sorted();
	});

	// Group words containing the same letters.
	for (auto next = begin, it = begin; it != end; it = next)
	{
		next = std::find_if(it, end, [it](const word_struct &e) -> bool {
			return e.sorted() != it->sorted();
		});

		// Append each pair of words containing the same letters to a list.
		// @timecomplexity: O(n^2) total.
		for (auto it2 = it + 1; it2 != next; ++it2)
		{
			for (auto it1 = it; it1 != it2; ++it1)
			{
				word_pair p1(*it1, *it2); // O(L) time
				if (filter.empty() || std::binary_search(
					filter.begin(), filter.end(), p1)) // O(L*log(m)) time
				{
					word_pairs.push_back(p1); // O(L) space
				}
				word_pair p2(*it2, *it1);
				if (filter.empty() || std::binary_search(
					filter.begin(), filter.end(), p2))
				{
					word_pairs.push_back(p2);
				}
			}
		}
	}

	// Sort the word pairs.
	// @timecomplexity O(L n^2 log n)
	std::sort(word_pairs.begin(), word_pairs.end());

	// Display the pairs.
	if (0)
	{
		for (auto it = word_pairs.begin(); it != word_pairs.end(); ++it)
		{
			//auto &word1 = it->first, &word2 = it->second;
			//std::cout << word1.word() << " -> " << word2.word() << " ["
			//	<< it->perm << "] Mask_1 = " << word1.mask() << std::endl;
		}
	}
}

// @timecomplexity: 
static bool max_square_anagram_pair(
	std::vector<word_struct>::iterator begin,
	std::vector<word_struct>::iterator end,
	int L)
{
	// Find all anagram pairs in the word list.
	// @timecomplexity  O(L n^2 log(n))
	// @spacecomplexity O(L n^2)
	std::vector<word_pair> word_pairs;
	find_anagram_pairs(begin, end, word_pairs, std::vector<word_pair>());
	if (word_pairs.empty())
		return false;

	// Find all square numbers of L digits: 10^(L-1) <= x^2 < 10^L
	std::string s(L, 0);
	int lb = (int)std::ceil(std::pow(10.0, (L-1)/2.0));
	int ub = (int)std::ceil(std::pow(10.0, L/2.0));
	std::vector<word_struct> squares;
	squares.reserve(ub - lb); // space: L*10^(L/2)
	for (int x = lb; x < ub; x++)
	{
		// Convert the digits of x^2 into a string for easier display.
		auto it = euler::rdigits<10>(x*x).begin();
		for (int i = 0; i < L; ++i, ++it)
		{
			s[L-1-i] = *it + '0';
		}

		// Computes the mask of the number. If this mask doesn't exist in
		// the word pair list at all, there is no need to append it.
		word_struct num(s);
		auto pos = std::lower_bound(word_pairs.begin(), word_pairs.end(),
			word_pair(num));
		if (pos != word_pairs.end() && pos->mask() == num.mask())
			squares.push_back(num);
	}

	// Find all anagram pairs in square numbers of L digits.
	std::vector<word_pair> square_pairs;
	find_anagram_pairs(squares.begin(), squares.end(), square_pairs, word_pairs);
	//std::cout << "There are " << square_pairs.size() << " square pairs." << std::endl;

	if (square_pairs.size() > 0)
	{
		// Find the largest pair by value.
		auto it = std::max_element(square_pairs.begin(), square_pairs.end(),
			[](const word_pair &p1, const word_pair &p2) -> bool {
				return p1.word() < p2.word();
		});
		std::cout << it->word() << std::endl;
		return true;
	}

	return false;
}

static void solve_problem_98()
{
	const int N = sizeof(Words) / sizeof(Words[0]);
	std::vector<word_struct> words(&Words[0], &Words[N]);

	// Sort the words by decreasing length.
	std::sort(words.begin(), words.end(), 
		[](const word_struct &w1, const word_struct &w2) -> bool {
			return w1.size() > w2.size();
	});

	// Group words of the same length, compute their letter mask, and
	// look for anagram pairs.
	for (auto it = words.begin(); it != words.end(); )
	{
		auto next = std::find_if(it, words.end(), [it](const word_struct &w) -> bool {
			return w.size() != it->size();
		});
		if (max_square_anagram_pair(it, next, (int)it->size()))
			break;
		it = next;
	}
}
